Search results for "discrete [space-time]"

Epichristoffel Words and Minimization of Moore Automata

2014

This paper is focused on the connection between the combinatorics of words and minimization of automata. The three main ingredients are the epichristoffel words, Moore automata and a variant of Hopcroft's algorithm for their minimization. Epichristoffel words defined in [14] generalize some properties of circular sturmian words. Here we prove a factorization property and the existence of the reduction tree, that uniquely identifies the structure of the word. Furthermore, in the paper we investigate the problem of the minimization of Moore automata by defining a variant of Hopcroft's minimization algorithm. The use of this variant makes simpler the computation of the running time and consequ…

On the Shuffle of Star-Free Languages

2012

Motivated by the general problem to characterize families of languages closed under shuffle, we investigate some conditions under which the shuffle of two star-free languages is star-free. Some of the special cases here approached give rise to new problems in combinatorics on words.

An elementary proof of Hilbertʼs theorem on ternary quartics

2012

Abstract In 1888, Hilbert proved that every nonnegative quartic form f = f ( x , y , z ) with real coefficients is a sum of three squares of quadratic forms. His proof was ahead of its time and used advanced methods from topology and algebraic geometry. Up to now, no elementary proof is known. Here we present a completely new approach. Although our proof is not easy, it uses only elementary techniques. As a by-product, it gives information on the number of representations f = p 1 2 + p 2 2 + p 3 2 of f up to orthogonal equivalence. We show that this number is 8 for generically chosen f, and that it is 4 when f is chosen generically with a real zero. Although these facts were known, there wa…

Some integral type fixed point theorems in Non-Archimedean Menger PM-Spaces with common property (E.A) and application of functional equations in dyn…

2013

In this paper, we prove some integral type common fixed point theorems for weakly compatible mappings in Non-Archimedean Menger PM-spaces employing common property (E.A). Some examples are furnished which demonstrate the validity of our results. We extend our main result to four finite families of self-mappings employing the notion of pairwise commuting. Moreover, we give an application which supports the usability of our main theorem.

The overlap algebra of regular opens

2010

Abstract Overlap algebras are complete lattices enriched with an extra primitive relation, called “overlap”. The new notion of overlap relation satisfies a set of axioms intended to capture, in a positive way, the properties which hold for two elements with non-zero infimum. For each set, its powerset is an example of overlap algebra where two subsets overlap each other when their intersection is inhabited. Moreover, atomic overlap algebras are naturally isomorphic to the powerset of the set of their atoms. Overlap algebras can be seen as particular open (or overt) locales and, from a classical point of view, they essentially coincide with complete Boolean algebras. Contrary to the latter, …

Inductive Inference with Procrastination: Back to Definitions

1999

In this paper, we reconsider the definition of procrastinating learning machines. In the original definition of Freivalds and Smith [FS93], constructive ordinals are used to bound mindchanges. We investigate possibility of using arbitrary linearly ordered sets to bound mindchanges in similar way. It turns out that using certain ordered sets it is possible to define inductive inference types different from the previously known ones. We investigate properties of the new inductive inference types and compare them to other types.

On the number of Arnoux–Rauzy words

2002

On the behaviour of measures of noncompactness with respect to differentiation and integration of vector-valued functions

1983

Criteria for the solubility and non-simplicity of finite groups

2005

Abstract Some criteria of the non-simplicity of a finite group by graph theoretical terms are derived. This is then used to establish conditions under which a finite group is soluble.

A note on renewal systems

1992

Abstract A renewal system is a symbolic dynamical system generated by free concatenations of a finite set of words. In this paper we prove that, given two systems which are both renewal and Markov systems, it is decidable whether they are topologically conjugate. The proof makes use of the methods and the techniques of formal language theory.